DP L

Competitive Game Read-Out Issues

DP with the board as the domain of definition

The board can be represented by a range

There is no need to distinguish between the first and the second hand.

Maximize "my score - opponent's score" for both the first and second moves.

Unmemorized naive recursion.

All sample codes succeed.

code:python

def solve(N, XS):

def first(L, R):

# debug(": L, R", L, R)

if L == R:

return max(

)

return first(0, N - 1)

Compile in Cython because it is TLE as it is.

I put in an array of impossible values to make sure that they have not been calculated, but since they can be both positive and negative, I also created an array with whether they have been calculated or not.

You could have left the value large enough.

I used "int" because using "bool" is an error.

code:cython

cdef first(L, R):

if L == R:

pos = L * N + R

else:

right = first(L + 1, R)

else:

left = first(L, R - 1)

if x > ret:

ret = x

return ret

cdef solve():

for i in range(N * N):

return first(0, N - 1)

def main():

global N, XS

# parse input

N = int(input())

XS = list(map(int, input().split()))

print(solve())

---